#include<stdio.h>

//顺序查找
int seq_search(int a[], int n, int k, int seek_seq[])
{
    int found = -1;//初始化为未找到
    for (int i = 0; i < n; i++)
    {
        seek_seq[i] = i;//记录当前访问的位置
        if (a[i] == k)
        {
            found = 0;//标记为找到
            for (int j = i + 1; j < n; j++)
            {
                seek_seq[j] = -1;
            }
            break;
        }
    }
    return found;
}

//二分查找
int bin_search(int a[], int n, int k, int seek_seq[])
{
    int left = 0;
    int right = n - 1;
    int mid;
    int count = 0;//记录seek_seq的当前索引
    int found = -1;

    while (left <= right)
    {
        mid = (left + right) / 2;
        seek_seq[count++] = mid;//记录当前访问的位置

        if (a[mid] == k)
        {
            found = 0;
            break;
        }else if (a[mid] < k)
        {
            left = mid + 1;
        }else
        {
            right = mid - 1;
        }
    }

    //查找失败，填充剩余的seek_seq
    while (count < n)
    {
        seek_seq[count++] = -1;
    }
    return found;
}

int main()
{
    //测试顺序查找
    int a1[] = {5,3,8,2,9};
    int n1 = sizeof(a1) / sizeof(a1[0]);
    int seek_seq1[n1];
    int target1 = 8;

    printf("sequential search test:\n");
    int result1 = seq_search(a1, n1, target1, seek_seq1);
    printf("search target:%d\n",target1);
    printf("search sequence:");
    for (int i = 0; i < n1; i++)
    {
        printf("%d ",seek_seq1[i]);
    }
    printf("\nResult: %s\n", result1 == 0 ? "success" : "failure");

    //测试二分查找
    int a2[] = {2,5,8,12,16,23,38,56};
    int n2 = sizeof(a2) / sizeof(a2[0]);
    int seek_seq2[n2];
    int target2 = 23;

    printf("\nBinary search test:\n");
    int result2 = bin_search(a2, n2, target2, seek_seq2);
    printf("search target:%d\n",target2);
    printf("search sequence:");
    for (int i = 0; i < n2; i++)
    {
        printf("%d ",seek_seq2[i]);
    }
    printf("\nResult:%s\n", result2 == 0 ? "success":"failure");

    return 0;
}